// 归并排序

function merge(arr) {
    const l = arr.length
    if (l < 2) return arr
    const m = Math.floor(l / 2)
    const arr1 = merge(arr.slice(0, m))
    const arr2 = merge(arr.slice(m))
    // 或者用splice
    // const arr1 = merge(arr.splice(0, m))
    // const arr2 = merge(arr)
    return mergeSort(arr1, arr2)
}

function mergeSort(arr1, arr2) {
    let arr = [];
    while (arr1.length && arr2.length) {
        if (arr1[0] <= arr2[0]) {
            arr.push(arr1.shift())
        } else {
            arr.push(arr2.shift())
        }
    }
    if (arr1.length) {
        arr.push(...arr1)
    }
    if (arr2.length) {
        arr.push(...arr2)
    }
    return arr;
}

function mergeSort2(arr1, arr2) {
    const l1 = arr1.length;
    const l2 = arr2.length;
    let arr = [];
    let i = 0, j = 0;
    while(i < l1 && j < l2) {
        if (arr1[i] <= arr2[j]) {
            arr.push(arr1[i++])
        } else {
            arr.push(arr2[j++])
        }
    }
    if (i == l1) {
        arr.push(...arr2.splice(j, l2))
    } else {
        arr.push(...arr1.splice(i, l1))
    }
    return arr
}


var arr = [5, 3, 2, 10, 8, 6, 7, 1, 4, 9]
console.log(merge(arr))


// 冒泡排序

function maopaoSort(arr) {
    const n = arr.length
    for (let i = 0; i < n - 1 ; i++) { // 排序轮数，n个数排n-1轮，i < n也没事，i最大值时，第二轮循环条件不满足直接进不去
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                let t = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = t
            }
        }
    }
}

var arr = [5, 3, 2, 10, 8, 6, 7, 1, 4, 9]
maopaoSort(arr)
console.log('冒泡：', arr)

// 插入排序   从下标1开始依次插入到[a[0]]有序数组中，未找到插入位置时边移动边遍历，

function charuSort(arr) {
    const n = arr.length
    for (let i = 1; i < n; i++) { // 循环要插入的数据，从下标1开始到结尾，默认arr[0]有序
        const t = arr[i]
        let j = i - 1
        for (; j >=0; j--) {
            if (t < arr[j]) {
                arr[j +1] = arr[j]
            } else {
                break;
            }
        }
        arr[j + 1] = t
    }
}
var arr = [5, 3, 2, 10, 8, 6, 7, 1, 4, 9]
charuSort(arr)
console.log('插入：', arr)
function charu2Sort(arr) {
    if (arr && arr.length < 2) {
        return;
    }
    for (let i = 1; i < arr.length; i++) {
        for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {  // 每次遇到比前边小的都交换
            let tmp = arr[j];
            arr[j] = arr[j + 1];
            arr[j+1] = tmp;
        }
    }
}

// 选择排序  每次选出最小的元素，与有序数组的尾部元素交换，初始从a[0]开始交换，
function xuanzeSort(arr) {
    const n = arr.length
    for (let i = 0; i < n - 1; i++) { // 控制排序趟数，n个数排序n-1次
        let k = i
        for(let j = i + 1; j < n; j++) {
            if (arr[k] > arr[j]) {
                k = j
            }
        }
        if (k != i) {
            let t = arr[i]
            arr[i] = arr[k]
            arr[k] = t
        }
    }
}
var arr = [5, 3, 2, 10, 8, 6, 7, 1, 4, 9]
xuanzeSort(arr)
console.log('选择：', arr)